home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graph / spanning.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.7 KB  |  94 lines

  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4.  
  5. main(int argc, char** argv)
  6. {
  7.  
  8. GRAPH<int,int>  G;
  9.  
  10. cmdline_graph(G,argc,argv);
  11.  
  12. edge x;
  13. forall_edges(x,G) G[x] = random(0,1000000);
  14.  
  15. edge_array<int>     cost1(G);
  16. edge_array<double>  cost2(G);
  17.  
  18. forall_edges(x,G) cost2[x] = cost1[x] = G[x];
  19.  
  20.  
  21. UGRAPH<int,int> U = G;
  22.  
  23. edge_array<int>   cost3(U);
  24.  
  25. forall_edges(x,U) cost3[x] = U[x];
  26.  
  27.  
  28. list<edge> el;
  29.  
  30. float T;
  31.  
  32. cout << "SPANNING_TREE:             ";
  33. cout.flush();
  34. T = used_time();
  35. el = SPANNING_TREE(G);
  36. cout << string(" %5.2f sec   |T| = %d",used_time(T),el.length());
  37. newline;
  38.  
  39. if (Yes("Print tree edges ? ")) 
  40.  forall(x,el) { G.print_edge(x); newline; }
  41.  
  42. el.clear();
  43.  
  44. cout << "MIN_SPANNING_TREE(int):    ";
  45. cout.flush();
  46. T = used_time();
  47. el = MIN_SPANNING_TREE(G,cost1);
  48. cout << string(" %5.2f sec   |T| = %d",used_time(T),el.length());
  49.  
  50. int total1 = 0;
  51. forall(x,el)  total1 += cost1[x];
  52.  
  53. cout << string("   total cost %d\n",total1);
  54.  
  55. if (Yes("Print tree edges ? ")) 
  56.  forall(x,el) { G.print_edge(x); newline; }
  57.  
  58.  
  59. el.clear();
  60.  
  61. cout << "MIN_SPANNING_TREE(ugraph): ";
  62. cout.flush();
  63. T = used_time();
  64. el = MIN_SPANNING_TREE(U,cost3);
  65. cout << string(" %5.2f sec   |T| = %d",used_time(T),el.length());
  66.  
  67. total1 = 0;
  68. forall(x,el)  total1 += cost3[x];
  69.  
  70. cout << string("   total cost %d\n",total1);
  71.  
  72. if (Yes("Print tree edges ? ")) 
  73.  forall(x,el) { G.print_edge(x); newline; }
  74.  
  75.  
  76.  
  77. cout << "MIN_SPANNING_TREE(double): ";
  78. cout.flush();
  79. T = used_time();
  80. el = MIN_SPANNING_TREE(G,cost2);
  81. cout << string(" %5.2f sec   |T| = %d",used_time(T),el.length());
  82.  
  83. double total2 = 0;
  84. forall(x,el)  total2 += cost2[x];
  85.  
  86. cout << string("   total cost %f\n",total2);
  87.  
  88. if (Yes("Print tree edges ? ")) 
  89.  forall(x,el) { G.print_edge(x); newline; }
  90.  
  91.  
  92. return 0;
  93. }
  94.